Day24 - Crypto 0x4 現代 - RSA

前言

• 昨天講完對稱式加密，今天來講講對稱式加密

RSA介紹

• RSA 是 Rivest、Shamir 和 Adelman 三位教授於 1978 年共同發表的一種加密 (encryption) 演算法
• 以兩個質數 (prime number) 作為加密與解密的兩個鑰匙(key)
  • 分別為公鑰 (public key) 和私鑰 (private key 或是secret key)
  • 長度從40 ~ 1024個bits
• 公鑰通常拿來加密，只有私鑰才能解密，相對於對稱式加密又更安全了一點，因為對稱式加密中，當其中的關鍵key被洩漏時，就會被破解

先備知識 - 歐拉

定義 : φ(n) 以下和 n 互質的數字個數
ex : φ(5) = 4 (有1,2,3,4 都與5互質)

p 為質數、k為整數

1. φ(p) = p-1

• 亦即 n 是某個質數的次方. 凡是 p 的倍數都不列入，總共有 k−1 個 p 的倍數

2. φ(p^k)=p^(k−1)×(p−1)
   • 例如要知道 φ(27), 因為 27=33, 故有 3, 2⋅3, 3⋅3..., 32⋅3, 總共 3^2個 3 的倍數.
   • ϕ(p^k)=p^k−p^(k−1)
3. φ(pq) = φ(p) * φ(q)

RSA找key流程

1. 找出兩個質數p,q
2. n=p*q
3. φ(n)=(p-1)(q-1)
   • $φ$為歐拉函數，
4. 找公鑰(e)
   • 1 < e < φ(n)
   • e要跟φ(n)互質，也就是gcd(e,φ(n)) = 1
5. 找私鑰(d)
   • ed$ % φ(n) = 1

• 加密
  • Alice => m^e(e是公鑰) mod n => C(密文)
• 解密
  • Bob => C^d mod$ n => m(明文)

example

1. 選兩個互質的數字(p = 5, q = 17)
2. 計算 n = p * q (n = 5 * 17 = 85)
3. 計算 φ(n) = (p-1) * (q-1)
   • φ(n) = 4 * 16 = 64
4. 選一個 e (與φ(n) 互質的數字) (e = 13)
5. 計算 d * e % φ(n) = 1 (d = 5)
6. 公鑰 {n, e} = {85, 13}、私鑰 {n, d} = {85, 5}

流程

1. 假設 Bob 要跟 Alice 說 10，則Bob 必須用 Alice 的公鑰去加密

   • $10^{13} % 85 = 45$

2. 當 Alice 收到 Bob 傳來的 45，則她必須用私鑰去解密

   • $45^{5} % 85 = 10$

歐拉定理 => RSA公鑰

• 安全性考慮
• 情況: 只有密文與公鑰
  • 傳輸過程: n,e,c
  • 解密:n,d,c
  • 透過公鑰(e)求密鑰(d)=>過程第五步
    • 必須要知道φ(n)，也就是你要知道p-1*q-1
    • 也就是說要p跟$q
    • 那也就是說要把n=p*q做質因數分解
    • 萬一n很大(通常是1024位的binary)，質因數分解就難到靠杯(不過量子電腦似乎解得出來)

對稱&非對稱加密比較

Ref

證明
http://jianiau.blogspot.com/2014/05/proof-of-rsa-algorithm.html